package study.Day_5;

/**
 * @Classname: Day_five
 * @Description: leetcode 第五题
 * @Date: 2021/9/28
 * @Author: huwei
 */

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * <p>
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 * <p>
 * 示例 3：
 * 输入：s = "a"
 * 输出："a"
 * <p>
 * 示例 4：
 * 输入：s = "ac"
 * 输出："a"
 */
public class Day_five {
    /**
     * 动态规划方法
     * <p>
     * 假如一个字符串是"ababa"记为p;对于"bab"是一个回文字符串记为s,那么"ababa"也是一个字符串
     * 因为它是s首尾加上一个a,假设s[i:j]表示一个字符串,i是起始位置,j是末尾位置.
     * 当s的首尾都加上一位,而这个两个字符一样.那么这个新字符串也必定是一个回文字符串.
     * 所以,可以得出结论 s[i:j]=s[i+1,j-1],
     * 但是这个字符串长度需要大于等于2,因为如果字符串长度是1,那么本身就是回文字符串
     * 如果字符串长度是2,那么就判断字符串中两个字符如果一样就是回文字符串,不一样就不是回文字符串
     */
    public String longestPalindrome(String s) {
        // 获取这个字符串的长度,如果这个长度小于2,那么这个字符串本身就是一个回文字符串.如:"a","b",这类的
        int len = s.length();
        if (len < 2) {
            return s;
        }
        // 初始化最大长度
        int maxLen = 1;
        // 初始化开始位置
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串,记为true
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        /**
         *  假如传入的是"ababa",则循环后 dp是
         *          0       1       2       3       4
         *  0     true
         *  1             true
         *  2                     true
         *  3                             true
         *  4                                     true
         */
        // 将s转成char字符数组便于比较
        char[] charArray = s.toCharArray();
        // 递推开始(设置起始位置为2,具体参考上方)
        for (int l = 2; l <= s.length(); l++) {
            // 设置左边界
            for (int i = 0; i < s.length(); i++) {
                // 设置右边界,由l和i确定右边界
                int j = l + i - 1;
                // 如果右边界越界,就退出循环
                if (j >= len) {
                    break;
                }
                // 如果i,j不是同一字符就表示s[i:j]不是回文字符串,在dp中记为false,否则就是true
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    // 考虑头尾去掉以后没有字符剩余，或者剩下一个字符的时候，肯定是回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        // 状态转移,将dp[i][j]的状态转移到dp[i][j]上,标记为true.
                        // 因为dp[i][j]是回文字符串,i+1=j-1,所以dp[i+1][j-1]也是回文字符串,
                        // 将dp[i][j]的标记赋值给dp[i+1][j-1]
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串
                // 此时更新记录回文长度和起始位置,寻找最长的字符串
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        // 返回回文字符串
        return s.substring(begin,begin+maxLen);
    }
}